package homework4;

public class LCS
{
	public int LCS_2N_Space(int[] x, int[] y)
	{
		if (x.length > y.length)
		{
			int[] tmp = x;
			x = y;
			y = tmp;
		}

		int[] a = new int[x.length];
		int[] b = new int[x.length];
		for (int j = 1; j < y.length; j++)
		{
			for (int i = 1; i < x.length; i++)
			{
				if (x[i] == y[j])
				{
					b[i] = a[i - 1] + 1;
				}
				else
				{
					if (a[i] >= b[i - 1])
					{
						b[i] = a[i];
					}
					else
					{
						b[i] = b[i - 1];
					}
				}
			}
			int[] tmp = a;
			a = b;
			b = tmp;
		}
		return a[a.length - 1];
	}

	public int LCS_N_Space(int[] x, int[] y)
	{
		if (x.length > y.length)
		{
			int[] tmp = x;
			x = y;
			y = tmp;
		}

		int[] c = new int[x.length];
		int tmp = 0, diagonal = 0;
		for (int j = 1; j < y.length; j++)
		{
			for (int i = 1; i < x.length; i++)
			{
				tmp = c[i];
				if (x[i] == y[j])
				{
					c[i] = diagonal + 1;
				}
				else
				{
					if (c[i - 1] > c[i])
					{
						c[i] = c[i - 1];
					}
				}
				diagonal = tmp;
			}
			diagonal = 0;
		}
		return c[c.length - 1];
	}

	public static void main(String[] args)
	{
		LCS lcs = new LCS();

		int[] x = { 0, 1, 1 };
		int[] y = { 0, 1, 1 };

		System.out.println(lcs.LCS_2N_Space(x, y));
		System.out.println(lcs.LCS_N_Space(x, y));
	}
}
